// https://www.lintcode.com/problem/closest-city/

public class Solution {
    /**
     * @param x: an array of integers, the x coordinates of each city[i]
     * @param y: an array of integers, the y coordinates of each city[i]
     * @param c: an array of strings that represent the names of each city[i]
     * @param q: an array of strings that represent the names of query locations
     * @return: the closest city for each query
     */
    public String[] NearestNeighbor(int[] x, int[] y, String[] c, String[] q) {
        // write your code here
        String[] ret = new String[q.length];
        Map<Integer, List<String>> mapX = new HashMap<>();
        Map<Integer, List<String>> mapY = new HashMap<>();
        Map<String, Integer[]> mapCity = new HashMap<>();
        for (int i = 0; i < c.length; ++i) {
            String city = c[i];
            if (!mapX.containsKey(x[i])) {
                mapX.put(x[i], new ArrayList<>());
            }
            mapX.get(x[i]).add(city);
            if (!mapY.containsKey(y[i])) {
                mapY.put(y[i], new ArrayList<>());
            }
            mapY.get(y[i]).add(city);
            if (!mapCity.containsKey(city)) {
                mapCity.put(city, new Integer[]{x[i], y[i]});
            }
        }
        for (int i = 0; i < q.length; ++i) {
            int dist = Integer.MAX_VALUE;
            String qcity = q[i];
            String rcity = "";
            Integer[] qpos = mapCity.get(qcity);
            int qx = qpos[0];
            int qy = qpos[1];
            System.out.println(qcity);
            if (mapX.containsKey(qx)) {
                for (String s : mapX.get(qx)) {
                    System.out.println("x： " + qx + ", " + s);
                    if (!s.equals(qcity)) {
                        Integer[] spos = mapCity.get(s);
                        int sdist = Math.abs(spos[1] - qy);
                        if (sdist < dist) {
                            dist = sdist;
                            rcity = s;
                        } else if (sdist == dist) {
                            if (s.compareTo(rcity) < 0) {
                                rcity = s;
                            }
                        }
                    }
                }
            }
            if (mapY.containsKey(qy)) {
                for (String s : mapY.get(qy)) {
                    System.out.println("y: " + qy + ", " + s);
                    if (!s.equals(qcity)) {
                        Integer[] spos = mapCity.get(s);
                        int sdist = Math.abs(spos[0] - qx);
                        if (sdist < dist) {
                            dist = sdist;
                            rcity = s;
                        } else if (sdist == dist) {
                            if (s.compareTo(rcity) < 0) {
                                rcity = s;
                            }
                        }
                    }
                }
            }
            if (!rcity.equals("")) {
                ret[i] = rcity;
            } else {
                ret[i] = "NONE";
            }
        }
        return ret;
    }
}